package com.ting.test.algorithms.大厂刷题班;

/**
 * 给定一个整数求是不是某个数的步骤和
 * 步骤和
 * 比如 681的步骤和为 681+68+6=
 * <p>
 * 思路
 * <p>
 * 如果一个数A大于另一个数B，那么A的步骤和也一定大于B
 * 利用二分法
 * 假设给定步骤和为C
 * 注意  步骤和C一定是大于他对应的那个数的
 * 从0~C开始使用二分法
 * 如果中间的值的步骤和大于C 那边表明目标数在右边，否则在左边
 * 继续二分
 * 如果最终能找到  表明存在 否则不存在
 */
public class 给定一个整数求是不是某个数的步骤和 {

    public static void main(String[] args) {
        int stepSum = 540;
        int target = process(stepSum, 0, stepSum);
//        int target = get(stepSum);
        System.out.printf(target+"");
    }

    private static int process(int stepSum, int L, int R) {

        if (L>=R) {
            return -1;
        }
        int mid = L + (R - L) / 2;
        int targetStepSum = get(mid);
        if (stepSum == targetStepSum) {
            return mid;
        } else if (stepSum > targetStepSum) {
            return process(stepSum, mid + 1, R);
        } else {
            return process(stepSum, L, mid - 1);
        }

    }

    private static int get(int mid) {
        int stepSum = mid;
        while (mid > 0) {
            mid = mid / 10;
            stepSum += mid;
        }
        return stepSum;
    }
}
